55. 跳跃游戏

Similar Question

Solution Tips

方案一: 暴力法 + 模拟

var canJump = function(nums) {
    if (nums.length === 1) {
        return true;
    }
    // 反过来看会不会更好呢? 看倒数第二个, 能不能去到 last
    // 再找到能去倒数第二的, 如果不能就从倒数第三看能不能去 last
    // 感觉又是回溯, 自从做完回溯了, 看啥都是回溯
    for (let i = nums.length - 2; i >= 0 ; i--) {
        let last = nums.length - 1;
        let j = i;
        while (j >= 0) {
            // 先找到一个能跳到last的,如果最终行不通就 next 呗
            if (nums[j] >= (last - j)) {
                last = j;
                j--;
            }
            else {
                j--;
            }
        }

        if (last === 0) {
            return true;
        }
    }

    return false;
};

方案二: 贪心

刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？

其实跳几步无所谓，关键在于可跳的覆盖范围！

不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

这个范围内，别管是怎么跳的，反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

局部最优推出全局最优，找不出反例，试试贪心！

这种方法所依据的核心特性：如果一个位置能够到达，那么这个位置左侧所有位置都能到达。 想到这一点，解法就呼之欲出了~

var canJump = function(nums) {
    if(nums.length === 1) return true
    let cover = 0
    for(let i = 0; i <= cover; i++) {
        cover = Math.max(cover, i + nums[i])
        if(cover >= nums.length - 1) {
            return true
        }
    }
    return false
};